264. 丑数 II

Similar Question

Solution Tips

方案一: 动态规划 + 模拟

最优化分析：4 和从 6 开始的所有丑数，都是在其前面的某个丑数乘以 2, 3, 5 的结果

就是从一个基准数 1 开始，算 1*2、1*3、1*5 的最小值，得出结果 1*2 最小，再将对应 Index++ 即可，结果就是每个数都会各自与 2 3 5 相乘，乘过了就轮到下一个

  var nthUglyNumber = function (n) {
    let index2 = 0, index3 = 0, index5 = 0
    let T = []
    T[0] = 1
    for (let i = 1; i < n; i++) {
      T[i] = Math.min(T[index2] * 2, T[index3] * 3, T[index5] * 5)
      if (T[i] === T[index2] * 2) index2++
      if (T[i] === T[index3] * 3) index3++
      if (T[i] === T[index5] * 5) index5++
    }
    return T[n - 1]
  };
  
  console.log(nthUglyNumber(1));